package graph;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;


class Edge {
	public int dest;//顶点在数组中的位置
	public int weight;//权重
	
	
	
	public Edge(int dest, int weight) {
		this.dest = dest;
		this.weight = weight;
	}
	public int getDest() {
		return dest;
	}
	public void setDest(int dest) {
		this.dest = dest;
	}
	public int getWeight() {
		return weight;
	}
	public void setWeight(int weight) {
		this.weight = weight;
	}
	public boolean equals(Object obj)
	{
		if (!(obj instanceof Edge))
			return false;

		return ((Edge)obj).dest == this.dest;
	}
	

}
class VertexInfo<T> {
	public T vertex;//顶点信息
	public List<Edge> edgeList;//关联节点
	public int inDegree;//顶点入度
	public int edgeNum;//顶点数
	
	public VertexState state;//顶点状态
	public int dateValue;
	public T parent;
	
	public boolean occupied;//时候修改标志

	public VertexInfo(T vertex) {
		this.vertex = vertex;
		edgeList = new LinkedList<Edge>();
		inDegree = 0;
		occupied = true;
	}
	
	
}
public class EGraph<T> implements Graph<T> {
	private Map<T, Integer> verMap;//顶点-对应的下标
	private List<VertexInfo<T>> vInfos;//顶点数组
	private Stack<Integer> vertextCache;//顶点缓存，当删除一个顶点，并没有真正删除，将其下表存入vertexCache中
	private int edgeNum;//边数
	private Set<T> graphVertexSet;
	public EGraph() {
		verMap = new HashMap<T, Integer>();
		vInfos = new ArrayList<VertexInfo<T>>();
		vertextCache = new Stack<Integer>();
		edgeNum = 0;
	}
	
	/**
	 * 添加一个顶点
	 * @param vertex
	 * @return
	 */
	public boolean addVertex(T v){
		int index;
		//已经存在的情况
		if(verMap.containsKey(v)){
			return false;
		}
		
		if(!vertextCache.isEmpty()){//顶点缓存不为空，从中取出一个顶点坐标，无需再去创建一个对象
			index = vertextCache.pop();
			VertexInfo<T> vertexInfo = vInfos.get(index);//取出可用的VertexInfo
			//清理工作
			vertexInfo.vertex = v;
			vertexInfo.edgeList.clear();// 清空边关系
			vertexInfo.inDegree = 0;
			vertexInfo.occupied = true;
		}else{
			index = vInfos.size();
			vInfos.add(new VertexInfo<T>(v));
		}
		verMap.put(v, index);
		return true;
	}
	//返回v对应的顶点在vInfos中的位置
	private int getVertexInfoIndex(T v){
		Integer index = verMap.get(v);
		return index == null?-1:index;
	}
	/**
	 * 返回v对应顶点所关联的邻结点
	 * @param v
	 * @return
	 */
	public Set<T> getNeighbors(T v){
		int index = getVertexInfoIndex(v);
		if(index == -1){
			return null;
		}
		Set<T> edgeSet = new HashSet<T>();
		VertexInfo<T> vertexInfo = vInfos.get(index);
		Edge edge = null;
		for (Iterator iterator = vertexInfo.edgeList.iterator(); iterator.hasNext();) {
			Edge e = (Edge) iterator.next();
			edgeSet.add(vInfos.get(e.dest).vertex);
		}
		return edgeSet;
	}
	/**
	 * 添加从v1指向v2一条边
	 * @param v1
	 * @param v2
	 * @param weight
	 * @return
	 */
	public boolean addEdge(T v1, T v2, int weight){
		int post1 = getVertexInfoIndex(v1);
		int post2 = getVertexInfoIndex(v2);
		//有不存在的点者返回false
		if(post1 == -1 || post2 == -1){
			throw new IllegalArgumentException("没有对应的节点");
		}
		if(post1 == post2){
			throw new IllegalArgumentException("起始点 和 结束点 不能相同");
		}
		Edge edge = new Edge(post2, weight);
		VertexInfo<T> vertexInfo1 = vInfos.get(post1);
		if(!vertexInfo1.edgeList.contains(edge)){//如果不存在v1 - v2 者加入
			vertexInfo1.edgeList.add(edge);
			vInfos.get(post2).inDegree ++;//v2对应的顶点入度自加
			edgeNum ++;//边数自加
		}else{
			return false;
		}
		return true;
	}
	/**
	 * 删除v1 - v2
	 * @param v1
	 * @param v2
	 * @return
	 */
	public boolean removeEdge(T v1, T v2){
		int post1 = getVertexInfoIndex(v1);
		int post2 = getVertexInfoIndex(v2);
		
		if(post1 == -1 || post2 == -1){
			throw new IllegalArgumentException("不存在这条边");
		}
		Edge edge = null;
		for (Iterator iterator = vInfos.get(post1).edgeList.iterator(); iterator.hasNext();) {
			edge = (Edge) iterator.next();
			if(edge.dest == post2){//存在v1 到 v2
				iterator.remove();
				vInfos.get(post2).inDegree --;
				edgeNum -- ;
				return true;
			}
			
		}
		return false;
	}
	//删除v对应的顶点
	public boolean removeVertex(T v){
		Integer index = verMap.get(v);
		if(index == null){//不存在该顶点
			return false;
		}
		verMap.remove(v);
		
		removeFixup(index);
		return true;
	}

	private void removeFixup(int index) {
		Edge edge = null;
		//1获得该索引对应的vertexInfo对象，将其occupied属性置为false,且将该索引存入缓存
		VertexInfo<T> vertexInfo = vInfos.get(index);
		
		vertexInfo.occupied = false;
		vertextCache.push(index);
		
		//2删除以该顶点为终点的所有边
		int len = vInfos.size();
		VertexInfo<T> vertexInfo2 = null;
		for(int i = 0; i < len ; i++){
			vertexInfo2 = vInfos.get(i);
			if(vertexInfo2.occupied){//v所对应的顶点已经为false
				for (Iterator iterator = vertexInfo2.edgeList.iterator(); iterator.hasNext();) {
					edge = (Edge) iterator.next();
					if(edge.dest == index){
						iterator.remove();
						edgeNum -- ;// 边数减一
						break;//跳出内层循环
					}
				}
			}
		}
		//3 删除所有从v出发的边
		edgeNum -= vertexInfo.edgeList.size();
		for (Iterator iterator = vertexInfo.edgeList.iterator(); iterator.hasNext();) {
			edge = (Edge) iterator.next();
			vertexInfo2 = vInfos.get(edge.dest);
			vertexInfo.inDegree --;
			iterator.remove();
		}
		
	}
	/**
	 * 判断图示后为空
	 * @return
	 */
	public boolean isEmpty(){
		return verMap.size() == 0;
	}
	/**
	 * 返回图中的边数
	 * @return
	 */
	public int numberOfEdges(){
		return edgeNum;
	}
	/**
	 * 返回图中的顶点数
	 * @return
	 */
	public int numberOfVertices(){
		return verMap.size();
	}
	public boolean containsEdge(T v1, T v2){
		int post1 = getVertexInfoIndex(v1);
		int post2 = getVertexInfoIndex(v2);
		
		if(post1 == -1 || post2 == -1){
			throw new IllegalArgumentException("参数错误");
		}
		VertexInfo<T> vertexInfo = vInfos.get(post1);
		Edge edge = null;
		for (Iterator iterator = vertexInfo.edgeList.iterator(); iterator.hasNext();) {
			edge = (Edge) iterator.next();
			if(edge.dest == post2){
				return true;
			}
		}
		return false;
	}
	
	public boolean containsVertex(T v){
		return verMap.containsKey(v);
	}
	/**
	 * 返回v1 与 v2 的权值
	 * @param v1
	 * @param v2
	 * @return
	 */
	public int getWeight(T v1, T v2){
		Edge edge = getEdge(v1, v2);
		if(edge == null){
			return -1;
		}
		return edge.weight;
		
	}
	/**
	 * 更新权值，返回-1更新失败，更新成功返回原先的值
	 * @param v1
	 * @param v2
	 * @param weight
	 * @return
	 */
	public int setWeight(T v1,T v2,int weight){
		Edge edge = getEdge(v1, v2);
		if(edge == null){
			return -1;
		}
		int preWeight = edge.weight;
		edge.weight = weight;
		return preWeight;
	}
	private Edge getEdge(T v1 , T v2){
		int post1 = getVertexInfoIndex(v1);
		int post2 = getVertexInfoIndex(v2);
		if(post1 == -1 || post2 == -1){
			throw new IllegalArgumentException("参数错误");
		}
		VertexInfo<T> vertexInfo = vInfos.get(post1);
		Edge edge = null;
		for (Iterator iterator = vertexInfo.edgeList.iterator(); iterator.hasNext();) {
			edge = (Edge) iterator.next();
			if(edge.dest == post2){
				return edge;
			}
		}
		return null;
	}
	public void clear(){
		
	}
	public Set<T> vertexSet(){
		if(graphVertexSet == null){
			graphVertexSet = new Set<T>() {

				@Override
				public boolean add(T e) {
					throw new UnsupportedOperationException();
				}

				@Override
				public boolean addAll(Collection<? extends T> c) {
					throw new UnsupportedOperationException();
				}

				@Override
				public void clear() {
					EGraph.this.clear();
					
				}

				@Override
				public boolean contains(Object o) {
					return verMap.containsKey(o);
				}

				@Override
				public boolean containsAll(Collection<?> c) {
					for (Iterator iterator = c.iterator(); iterator.hasNext();) {
						Object object = (Object) iterator.next();
						if(!verMap.containsKey(object)){
							return false;
						}
					}
					return true;
				}

				@Override
				public boolean isEmpty() {
					return verMap.size() == 0;
				}

				@Override
				public Iterator<T> iterator() {
					// TODO Auto-generated method stub
					return new IteratorImpl();
				}

				@Override
				public boolean remove(Object o) {
					if(verMap.containsKey(o)){
						removeVertex((T) o);
						return true;
					}
					return false;
				}

				@Override
				public boolean removeAll(Collection<?> c) {
					for (Iterator iterator = c.iterator(); iterator.hasNext();) {
						Object object = (Object) iterator.next();
						if(!remove(object)){
							return false;
						}
					}
					return true;
				}

				@Override
				public boolean retainAll(Collection<?> c) {
					// TODO Auto-generated method stub
					return false;
				}

				@Override
				public int size() {
					// TODO Auto-generated method stub
					return verMap.size();
				}

				@Override
				public Object[] toArray() {
					// TODO Auto-generated method stub
					return null;
				}

				@Override
				public <T> T[] toArray(T[] a) {
					// TODO Auto-generated method stub
					return null;
				}
			};
		}
		return graphVertexSet;
		
	}
	private class IteratorImpl implements Iterator<T>{
		private Iterator<T> iter;
		T lastValue = null;
		public IteratorImpl() {
			iter =  verMap.keySet().iterator();
		}

		@Override
		public boolean hasNext() {
			
			return iter.hasNext();
		}

		@Override
		public T next() {
			lastValue = iter.next();
			return lastValue;
			
		}

		@Override
		public void remove() {
			if(lastValue == null){
				throw new IllegalStateException("还未调用next()方法，不可调用remove()方法");
			}
			int index = getVertexInfoIndex(lastValue);
			iter.remove();
			//清理工作
			removeFixup(index);
		}
		
	}
	public VertexState getState(T v){
		int post = getVertexInfoIndex(v);
		if(post == -1){
			throw new IllegalArgumentException("参数错误");
		}
		return vInfos.get(post).state;
	}
	/**
	 * 全部节点设为未访问
	 */
	public void allUnVisted(){
		VertexInfo<T> vertexInfo = null;
		int len = vInfos.size();
		for(int i = 0; i < len ; i++){
			vertexInfo = vInfos.get(i);
			if(vertexInfo.state != VertexState.UNVISITED){
				vertexInfo.state = VertexState.UNVISITED;
			}
		}
	}

	@Override
	public VertexState setState(T v, VertexState state) {
		int post = getVertexInfoIndex(v);
		if(post == -1){
			throw new IllegalArgumentException("参数错误");
		}
		VertexInfo<T> vertex = vInfos.get(post);
		VertexState preState = vertex.state;
		vertex.state = state;
		return preState;
	}
	
	
}



